1. Field of the Invention
The invention relates to a method for solving carpool matching problem and a carpool server using the same.
2. Description of Related Art
Due to economic development in recent years which has resulted in industrialization and urbanization, the number of vehicles on roadways has risen rapidly, making traffic congestion an increasingly serious problem in large cities around the world. Severe traffic congestion causes various negative effects including air pollution, loss of valuable time, consumption of fuel, and so on. Public transport systems can reduce traffic congestion effects but unfortunately cannot provide as much flexibility, comfort, and freedom as a private vehicle. For this reason, private vehicles are far and away the dominant commuting method. However, because these private vehicles are often used to transport just one or two people, there are a lot of empty seats on the road. For example, in the UK the average vehicle only has 1.5 people in it. It is obvious that considerable effort is required to solve the above-mentioned problem.
Carpooling is an environmentally friendly transportation system based on the sharing of the empty seats of vehicles, and is one of the most effective solutions to traffic congestion. Drivers share their cars with one or more additional passengers who have a similar destination. By doing so, the occupancy rate of cars could be increased substantially by reducing the number of empty seats in these vehicles. Fewer vehicles would be required to transport the same number of people to their destinations, resulting in a significantly lower number of cars on the road. Additional benefits of carpooling include shared travel costs, reduced energy consumption, and lowered vehicle emissions, among others.
In effort to provide a carpool service, many systems have been proposed which can be broadly classified into two categories according to their features. The first category is website-based and broadcasts the carpool information to an online community platform. These kind of online community platforms provide an interface between the passengers who are looking for a shared ride and the drivers who are offering their vehicle for the shared ride. The carpool users can search all the posted carpool plans and make contact with the provider of the plan which interests them. However, these website-based carpool systems lack integration of geographic information system (GIS) support and thus cannot effectively deal with instant carpool intuitional operation requirements. The second category not only provides a website-based carpool services but also utilizes a digital GIS map to match ride offers to requests. For example, the users of some of the carpool platforms can easily make their carpool requests or offers through the map-based interface. Moreover, some of the carpool platforms also provide a route service based on GIS. However, the applicability of this system in instant scenarios is limited because these systems cannot support the use of the Global Positioning System (GPS) handheld navigation device that provides carpool users with their current location information.
Numerous carpool systems have been proposed to solve traffic congestion problems. Some website-based systems provide basic carpool functions such as the ability to send a carpool request in a given date and time, and then seek suitable carpool partners to meet the demand. Furthermore, several carpool systems integrate a digital GIS map to offer a visual experience with accurate geographical information to those seeking carpool partners. However, these traditional carpool systems are very inconvenient and inefficient for the user who requires real-time carpool matching service. Besides, complexity increases rapidly as the number of carpool users and thus the number of possible solutions grows. Therefore, how to find solutions in a reasonable time becomes a very important issue.
Besides, although there are some algorithms proposed for solving cargo delivery routing problems, these algorithms cannot be directly applied to solve carpool problems. For example, the departing point and the last destination are the same in the cargo delivery routing problems, which is obviously different from ordinary carpool situations. Besides, the time schedule of a driver to delivery cargos is usually fixed, such that the algorithms for solving cargo delivery routing problems may not be able to handle real-time carpool problems.